package com.li.algorithm.leetcode.hot100;

import java.util.HashMap;

public class Test10 {
    public int subarraySum(int[] nums, int k) {
        int result = 0;
        //TODO: 从第一个数、第二个数、第三个数开始，加到==k
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    result++;
                }
            }
        }
        return result;
    }


    /**
     * 前缀和解法
     * 1. 当前公式不易发现线索时，移项
     * 2. 利用map数据结构提高效率
     */
    public int subarraySum2(int[] nums, int k) {
        int result = 0;
        //TODO:计算前缀和
        // TODO: ans[j] - ans[i-1] = k
        // TODO: ans[i-1] = ans[j] - k
        // TODO: 找到所有满足这一条件的前缀位置
        // TODO: 将所有前缀和存入map(prefix, count)
        // TODO: 查询 map.get(prefix-k)
        HashMap<Integer, Integer> map = new HashMap<>();
        int pre = 0;
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            int value = pre + nums[i];
            Integer count = map.get(value - k);
            if (count != null) {
                result += count;
            }
            map.merge(value, 1, Integer::sum);
            pre = value;
        }
        return result;
    }

    public static void main(String[] args) {
        Test10 test10 = new Test10();
        System.out.println(test10.subarraySum2(new int[]{1}, 0));
    }
}
